Two propositions \(P(p,q,\ldots)\) and \(Q(p,q,\ldots)\) are said to be logically equivalent, or simply equivalent or equal, denoted by
\(P(p,q,\ldots) \equiv Q(p,q,\ldots)\)
if they have identical truth tables. Consider, for example, the truth tables of \(\neg (p \wedge q)\) and \(\neg p \vee \neg q\) appearing in Fig. 10-6. Observe that both truth tables are the same, that is, both propositions are false in the first case and true in the other three cases. Accordingly, we can write
\(\neg (p \wedge q) \equiv \neg p \vee \neg q\)
In other words, the propositions are logically equivalent.
| \(p\) | \(q\) | \(p \wedge q\) | \(\neg (p \wedge q)\) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
| \(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \(\neg p \vee \neg q\) |
|---|---|---|---|---|
| T | T | F | F | F |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
Remark: Consider the statement
“It is not the case that roses are red and violets are blue”
This statement can be written in the form \(\neg (p \wedge q)\), where \(p\) is “roses are red” and \(q\) is “violets are blue.” However, as noted above, \(\neg (p \wedge q) \equiv \neg p \vee \neg q\). Thus the statement
“Roses are not red, or violets are not blue”
has the same meaning as the given statement.
Propositions satisfy various laws which are listed in Table 10-1. (In this table, T and F are restricted to the truth values “true” and “false” respectively.) We state this result formally.
| Law | Expression |
|---|---|
| Idempotent laws | \(p \vee p \equiv p\) \(p \wedge p \equiv p\) |
| Associative laws | \((p \vee q) \vee r \equiv p \vee (q \vee r)\) \((p \wedge q) \wedge r \equiv p \wedge (q \wedge r)\) |
| Commutative laws | \(p \vee q \equiv q \vee p\) \(p \wedge q \equiv q \wedge p\) |
| Distributive laws | \(p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\) \(p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)\) |
| Identity laws | \(p \vee \text{F} \equiv p\) \(p \wedge \text{T} \equiv p\) |
| Domination laws | \(p \vee \text{T} \equiv \text{T}\) \(p \wedge \text{F} \equiv \text{F}\) |
| Complement laws | \(p \vee \neg p \equiv \text{T}\) \(p \wedge \neg p \equiv \text{F}\) |
| DeMorgan’s laws | \(\neg (p \vee q) \equiv \neg p \wedge \neg q\) \(\neg (p \wedge q) \equiv \neg p \vee \neg q\) |
| Involution law | \(\neg (\neg p) \equiv p\) |
Many statements, particularly in mathematics, are of the form “If \(p\) then \(q\)”. Such statements are called conditional statements, and are denoted by
\(p \rightarrow q\)
The conditional \(p \rightarrow q\) is frequently read “\(p\) implies \(q\)” or “\(p\) only if \(q\)”.
Another common statement is of the form “\(p\) if and only if \(q\)”. Such statements are called biconditional statements, and are denoted by
\(p \leftrightarrow q\)
The truth values of \(p \rightarrow q\) and \(p \leftrightarrow q\) are defined by the tables in Fig. 10-7. Observe that:
| \(p\) | \(q\) | \(p \rightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
| \(p\) | \(q\) | \(p \leftrightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Example 1: “If it rains, then the ground is wet.”
Let \(p\) = “It rains”, \(q\) = “The ground is wet”.
Thus, a conditional is false only when the hypothesis is true but the conclusion is false.
Example 2: “If you study hard, then you will pass the exam.”
Let \(p\) = “You study hard”, \(q\) = “You pass the exam”.
The statement is only false when you study but still fail.
Example 1: “You can vote if and only if you are at least 18 years old.”
Let \(p\) = “You can vote”, \(q\) = “You are at least 18 years old”.
A biconditional is true only when both parts have the same truth value.
Example 2: “A triangle is equilateral if and only if all its angles are 60°.”
Let \(p\) = “Triangle is equilateral”, \(q\) = “All angles are 60°”.
The biconditional holds because the two properties are equivalent.
The truth table of the proposition \(\neg p \lor q\) appears in Fig. 10-8. Observe that the truth tables of \(\neg p \lor q\) and \(p \to q\) are identical, that is, they are both false only in the second case. Accordingly, \(p \to q\) is logically equivalent to \(\neg p \lor q\); that is,
\(p \to q \equiv \neg p \lor q\)
In other words, the conditional statement “If \(p\) then \(q\)” is logically equivalent to the statement “Not \(p\) or \(q\)” which only involves the connectives \(\lor\) and \(\neg\) and thus was already a part of our language. We may regard \(p \to q\) as an abbreviation for an oft-recurring statement.
| \(p\) | \(q\) | \(\neg p\) | \(\neg p \lor q\) |
|---|---|---|---|
| T | T | F | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
An argument is an assertion that a given set of propositions \(P_{1}, P_{2}, \ldots, P_{n}\), called premises, yields (has as a consequence) another proposition \(Q\), called the conclusion. Such an argument is denoted by
\(P_{1}, P_{2}, \ldots, P_{n} \vdash Q\)
The notion of a “logical argument” or “valid argument” is formalized as follows.
Example 1 (Valid Argument — Law of Detachment):
“If it is raining, then the streets are wet. It is raining. Therefore, the streets are wet.”
Let \(p\) = “It is raining”, \(q\) = “The streets are wet”.
Form: \(p \to q,\; p \;\vdash\; q\)
| \(p\) | \(q\) | \(p \to q\) | Premises true? | Conclusion |
|---|---|---|---|---|
| T | T | T | ✅ | q = T ✅ |
| T | F | F | ❌ | — |
| F | T | T | ❌ | — |
| F | F | T | ❌ | — |
✅ Valid: Whenever both premises are true (only row 1), the conclusion is also true.
Example 2 (Invalid Argument — Fallacy):
“If it is raining, then the streets are wet. The streets are wet. Therefore, it is raining.”
Let \(p\) = “It is raining”, \(q\) = “The streets are wet”.
Form: \(p \to q,\; q \;\vdash\; p\)
| \(p\) | \(q\) | \(p \to q\) | Premises true? | Conclusion |
|---|---|---|---|---|
| T | T | T | ✅ | p = T ✅ |
| T | F | F | ❌ | — |
| F | T | T | ✅ | p = F ❌ |
| F | F | T | ❌ | — |
❌ Invalid (Fallacy): In row 3, both premises are true but the conclusion is false. The streets could be wet from a sprinkler, not rain.
Example 3 (Valid Argument — Law of Syllogism):
“If you study, you will get good grades. If you get good grades, you will graduate with honors. Therefore, if you study, you will graduate with honors.”
Let \(p\) = “You study”, \(q\) = “You get good grades”, \(r\) = “You graduate with honors”.
Form: \(p \to q,\; q \to r \;\vdash\; p \to r\)
✅ Valid: By the Law of Syllogism, the conclusion follows necessarily from the premises.
Example 4 (Invalid Argument — Denying the Antecedent):
“If you are a citizen, then you can vote. You are not a citizen. Therefore, you cannot vote.”
Let \(p\) = “You are a citizen”, \(q\) = “You can vote”.
Form: \(p \to q,\; \neg p \;\vdash\; \neg q\)
| \(p\) | \(q\) | \(p \to q\) | \(\neg p\) | Premises true? | \(\neg q\) |
|---|---|---|---|---|---|
| T | T | T | F | ❌ | — |
| T | F | F | F | ❌ | — |
| F | T | T | T | ✅ | F ❌ |
| F | F | T | T | ✅ | T ✅ |
❌ Invalid (Fallacy): In row 3, the premises are true (you are not a citizen, and the conditional holds) but the conclusion “you cannot vote” is false — you might be a permanent resident who can vote in local elections.
Now the propositions \(P_{1}, P_{2}, \ldots, P_{n}\) are true simultaneously if and only if the proposition \(P_{1} \wedge P_{2} \wedge \cdots \wedge P_{n}\) is true. Thus the argument \(P_{1}, P_{2}, \ldots, P_{n} \vdash Q\) is valid if and only if \(Q\) is true whenever \(P_{1} \wedge P_{2} \wedge \cdots \wedge P_{n}\) is true or, equivalently, if the proposition \((P_{1} \wedge P_{2} \wedge \cdots \wedge P_{n}) \to Q\) is a tautology. We state this result formally.
We apply this theorem in the next example.
A fundamental principle of logical reasoning states:
“If \(p\) implies \(q\) and \(q\) implies \(r\), then \(p\) implies \(r\)”
That is, the following argument is valid:
\(p \to q,\; q \to r \;\vdash\; p \to r\) (Law of Syllogism)
This fact is verified by the truth table in Fig. 10-10, which shows that the following proposition is a tautology:
\([(p \to q) \wedge (q \to r)] \to (p \to r)\)
Equivalently, the argument is valid since the premises \(p \to q\) and \(q \to r\) are true simultaneously only in Cases (rows) 1, 5, 7, 8 and in these cases the conclusion \(p \to r\) is also true. (Observe that the truth table required \(2^{3} = 8\) lines since there are three variables, \(p, q, r\).)
| \(p\) | \(q\) | \(r\) | \(p \to q\) | \(q \to r\) | \((p \to q) \wedge (q \to r)\) | \(p \to r\) | \([(p \to q) \wedge (q \to r)] \to (p \to r)\) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | F | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
We now apply the above theory to arguments involving specific statements. We emphasize that the validity of an argument does not depend upon the truth values nor the content of the statements appearing in the argument, but upon the particular form of the argument. This is illustrated in the following example.
Consider the following argument:
\(S_{1}\): If a man is a bachelor, he is unhappy.
\(S_{2}\): If a man is unhappy, he dies young.
\(S\): Bachelors die young.
Here the statement \(S\) below the line denotes the conclusion of the argument, and the statements \(S_{1}\) and \(S_{2}\) above the line denote the premises. We claim that the argument \(S_{1}, S_{2} \vdash S\) is valid. For the argument is of the form
\(p \to q,\; q \to r \;\vdash\; p \to r\)
where \(p\) is “He is a bachelor”, \(q\) is “He is unhappy” and \(r\) is “He dies young”; and by Example 10.6 this argument (law of syllogism) is valid.